package data_structure;

import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * https://www.cnblogs.com/fengzhiwu/p/5524324.html
 * <p>
 * hash
 * hash            hash
 * hash    hash    hash    hash
 * |       |       |       |
 * A       B       C       D
 * </p>
 */
public class MerkleTree {

    private String root;

    private List<String> merkleNode;

    @Before
    public void init() {
        merkleNode = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            merkleNode.add(i + "");
        }
    }

    @Test
    public void merkleTree() {
        print("叶子数据: ", merkleNode);
        int i = 1;
        List<String> tempList = merkleNodeHash(merkleNode);
        print("倒数第" + i++ + "层: ", tempList);
        while (tempList.size() != 1) {
            tempList = merkleNodeHash(tempList);
            print("倒数第" + i++ + "层: ", tempList);
        }
        root = tempList.get(0);
        System.out.println("跟hash: " + root);
    }


    private List<String> merkleNodeHash(List<String> merkleNode) {
        List<String> temp = new ArrayList<>(((merkleNode.size() + 1) / 2));

        int index = 0;
        while (index < (merkleNode.size() - 1)) {
            String left = merkleNode.get(index++);
            if (left == null) {
                left = "";
            }
            String right = merkleNode.get(index++);
            if (right == null) {
                right = "";
            }
            temp.add((left + right).hashCode() + "");
        }
        return temp;
    }


    private void print(String remark, List<String> merkleNode) {
        System.out.println(remark);
        merkleNode.forEach(s -> System.out.print(s + "\t"));
        System.out.println();
    }


}
